(1) Technical Field
The present invention relates to a method and software tool for evaluation of Bayesian Network (BN) models for decision support. More specifically, the present invention relates to a technique for predicting the accuracy of a BN model and determining what parameters may be providing inaccuracies in the model either because of inaccurate modeling or because of real-world observations.
(2) Discussion
The advent of artificial intelligence within computer science has generated an abundance of decision-support systems. Decision-support systems are computer systems in which decisions, typically rendered by humans, are recommended and sometimes made. In creating decision-support systems, computer scientists seek to provide decisions with as high a level of accuracy as possible. Thus, computer scientists strive to create decision-support systems that are equivalent to or more accurate than a human expert. Applications of decision-support systems include medical diagnosis, troubleshooting computer networks, or other systems where a decision is based upon identifiable criteria.
Bayesian networks (BN), known also as belief networks, are one example of a modeling technology on which decision-support system can be based. BN models are graphical probabilistic models that result from combining graph and probability theories. The BN models can be created using information obtained from experts, from design documentation, and from data. BN models can also be learned entirely from data.
Before BN models can be used in decision support aids, they have to be extensively evaluated. A typical evaluation relies on comparing the answers suggested by the BN models with those expected by the experts. The evaluation is generally limited to a relatively small number of decision cases, for which the experts know the correct answer.
A conventional evaluation of BN models is typically based on a limited ad-hoc testing. First, a set of cases is identified for which a correct decision is known. The cases may come from the data or from the expert. Then, the BN is queried for decision recommendations based on the evidence available in the cases. The quality of the BN model is determined on the basis of comparison the recommendations produced by the model for the cases with the correct decisions. The number of the cases is usually very limited and their selection is driven by their availability rather than proper coverage of the decision domain. The conventional evaluation is almost always incomplete and therefore unreliable. What is needed is a systematic approach for evaluating the performance of a BN model.
In D. Heckerman, J. S. Breese, K. Rommlese “Decision-Theoretic Troubleshooting,” Communications of ACM, March 1995, Vol. 38, No. 3, pp. 49-57, planning of test and repair sequences for cost-optimal troubleshooting is described. The systems under going troubleshooting are modeled using BN. The paper describes finding the ordering of test and repair steps that results in minimal cost of troubleshooting. Monte Carlo methods are applied to generate test examples from the BN. The examples are the basis of comparison of the author's planning method and other methods known in the literature.
In U.S. Pat. No. 5,802,256 to D. Heckerman, D. Geiger, D. M. Chickering, entitled “Generating Improved Belief Networks” a method for creating BN models for decision support problems from expert knowledge and from data is described. The '256 patent describes integrating the two sources of information to obtain a model of better performance than that originating from data or expert knowledge only. The BN is created using a software tool referred to as a network generator.
A technical problem faced by all those who use BN in real-life decision support is that the BN models are designed for critical decision support problems, e.g. diagnostics, and are very complex and, as such, need to be very carefully evaluated before they can be used in practice. Thus to accomplish this evaluation task, an automated evaluation method, which covers all the parts of the model and all the most probable decision cases, is needed.